package main.java.indi.zyj.c150.dps;

public class _11_EightQueens {


    static boolean[] col = new boolean[10];
    static boolean[] diagonal1 = new boolean[20];
    static boolean[] diagonal2 = new boolean[20];
    static int ans = 0;


    //  检查这位置是否可以用
    static boolean check(int r, int c){
        return !col[c] && !diagonal1[r + c] && !diagonal2[r - c + 8];
    }

    //  遍历到第row行
    static void Dfs(int r){

        if (r == 8){
            ans++;
            return;
        }

        for (int i = 0; i < 8; i++) {
            if (check(r, i)){
                col[i] = diagonal1[r + i] = diagonal2[r - i + 8] = true;
                Dfs(r + 1);
                col[i] = diagonal1[r + i] = diagonal2[r - i + 8] = false;
            }
        }
    }



    public static void main(String[] args) {
        Dfs(0);
        System.out.println(ans);
    }


}
